package com.sise.Tree;

/**
 *      100_相同的树
 *      给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 *      如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 *
 *      解题思路：
 *          递归：检查当前两棵树的左右节点是否都为空，或者都不为空，如果满足以上条件的话，那么就判断 节点数值 是否相等，
 *          如果当前两个节点的数值相等，那么就递归 判断它们的左子树、右子树
 *
 *          1、终止条件：     当两个节点不一样的时候就终止
 *          2、返回什么信息：   返回当前两颗树 是否相等，false
 *          3、本机递归应该返回什么：   判断是否相等，递归调用其子树
 */

public class _100_isSameTree {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如果两个节点都为 null，那么就说明遍历到根节点，返回 true 即可
        if (p == null && q == null) return true;

        // 经过上一行代码的过滤后，现在只有两种情况，  一：其中一个为空，  二：两个都不为空；
        // 故此如果一个为空，一个不为空的情况下，就说明不相等
        if (p == null || q == null) return false;

        // 这里比较的是数值大小 val，如果少了val，那么代表的就是 内存地址
        if (p.val == q.val){
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }else {
            return false;
        }
    }
}
